Genomy

Limit pamięci: 32 MB

Biolodzy zajmujący się genetyką porównawczą poszukują sekwencji genów zachowanych w pewnym zbiorze gatunków.

Niech zbiór liczb oznacza geny - każdej liczbie odpowiada jeden gen. Każdy z gatunków określony jest permutacją liczb , która oznacza uporządkowanie jego genów. Ciąg genów jest zachowaną sekwencją genów w zbiorze gatunków, jeśli jest on podciągiem (niekoniecznie spójnym) uporządkowania genów każdego z tych gatunków.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis sekwencji genów,
• wyznaczy długość najdłuższej zachowanej sekwencji,
• zapisze odpowiedź na standardowe wyjście.

Wejście

W pierwszej linii standardowego wejścia znajdują się dwie liczby całkowite i oddzielone pojedynczym odstępem, przy czym oraz . Liczba oznacza liczbę genów, a liczbę gatunków. Każda z następnych linii zawiera genom kolejnego gatunku zapisany jako permutacja liczb pooddzielanych pojedynczymi odstępami.

Wyjście

Na wyjściu powinna zostać wypisana dokładnie jedna liczba całkowita równa długości najdłuższej zachowanej sekwencji genów.

Przykład

Dla danych wejściowych:

5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

poprawną odpowiedzią jest:

3

Wyjaśnienie

Podciągi: są zachowanymi sekwencjami genów wśród tych 3 gatunków. Najdłuższą zachowaną sekwencją genów tych 3 gatunków jest .

Autor zadania: Marcin Stefaniak.